最长重复子串

[编程题]最长重复子串

热度指数：18688 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

定义重复字符串是由两个相同的字符串首尾拼接而成。例如："abcabc" 是一个长度为 6 的重复字符串，因为它由两个 "abc" 串拼接而成；"abcba" 不是重复字符串，因为它不能由两个相同的字符串拼接而成。

给定一个字符串，请返回其最长重复子串的长度。

若不存在任何重复字符子串，则返回 0。

本题中子串的定义是字符串中一段连续的区间。

数据范围：字符串长度不大于 $10^3$ ，保证字符串一定由小写字母构成。

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n^2)$

示例1

输入

"ababc"

输出

说明

abab为最长的重复字符子串，长度为4

示例2

输入

"abcab"

输出

说明

该字符串没有重复字符子串

算法知识视频讲解

Python 3

牛客607605057号

class Solution:
def solve(self , a: str) -> int:
# write code here
n = len(a)//2
while n>0:
for i in range(len(a)-2*n+1):
if a[i:i+n] == a[i+n:i+2*n]:
return 2*n
n-=1
return 0

发表于 2022-06-16 22:10:28 回复(0)

Python 3

Joy_9

class Solution:
    def solve(self , a: str) -> int:
        # write code here
        size=len(a)//2
        max_len=0
        while size>0:
            for i in range(len(a)-2*size+1):
                if a[i:i+size]==a[i+size:i+2*size]:
                    max_len=max(max_len,2*size)
                    break
            size-=1
        return max_len

发表于 2022-01-23 07:19:23 回复(0)

Python 3

TILL201903151825511

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param a string字符串 待计算字符串
# @return int整型
#
class Solution:
    def solve(self , a ):
        # write code here
        res = 0
        if not a&nbs***bsp;len(a)<2: return 0
        l = len(a)
        for i in range(l//2, 0, -1): # 这段字符串可能的长度
            for j in range(l-i): # 第一个字符串可能的起点
                if a[j]==a[i+j]: res+=1
                else: res = 0
                if res == i: return i*2
        return 0

发表于 2021-07-30 18:58:52 回复(0)

Python 3